package demo1;

import java.util.Set;

public class Solution {

    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] breaked = new boolean[s.length()+1];
        breaked[0] = true;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length();j++) {
                if (breaked[j] && dict.contains(s.substring(j+1,i))) {
                    breaked[i] = true;
                    break;
                }
            }
        }
        return breaked[s.length()];
    }
}